package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-28
 * Time:16:09
 */

/**
 *
 牛客算法篇:BM20 数组中的逆序对
 描述
 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
 数据范围：  对于 50%50% 的数据, size≤104size≤104
 对于 100%100% 的数据, size≤105size≤105
 数组中所有数字的值满足 0≤val≤1090≤val≤109
 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
 输入描述：
 题目保证输入的数组中没有的相同的数字
 示例1
 输入：
 [1,2,3,4,5,6,7,0]
 返回值：
 7
 */
public class InversePairs {
    public static void main(String[] args) {
        InversePairs(new int[]{7,5,6,4});
    }
    private static final int MOD = 1000000007;
    public static int InversePairs(int[] nums) {
        // write code here
        if (nums == null || nums.length == 1){
            return 0;
        }
        int[] tmp = new int[nums.length];
        return merge(nums,tmp,0,nums.length - 1);
    }

    private static int merge(int[] nums, int[] tmp, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int count = merge(nums,tmp,left,mid) + merge(nums,tmp,mid + 1,right);
        int i = mid,j = right,k = right;
        while (i >= left && j >= mid + 1){
            if (nums[i] > nums[j]){
                tmp[k--] = nums[i--];
                count = (count + j - mid) % MOD;
            }else {
                tmp[k--] = nums[j--];
            }
        }
        while (i >= left){
            tmp[k--] = nums[i--];
        }
        while (j >= mid + 1){
            tmp[k--] = nums[j--];
        }
        for (k = left; k <= right; k++) {
            nums[k] = tmp[k];
        }
        return count;
    }
}
